#include "LabelHelper.h"

LabelHelper::LabelHelper( Graph& graph ) : g( graph ) { }

// merge strongly connected components
void LabelHelper::mergeStronglyCC() {

    // store the component result
    int n = num_vertices( g );
	
    VertexIndexMap index_map = get(&VertexProp::id, g);
    std::vector<int> component(num_vertices(g));
    iterator_property_map < int*, VertexIndexMap, int, int&>
	iter_map(&component[0], index_map);
    int num = strong_components(g, iter_map, vertex_index_map( get( &VertexProp::id, g ) ) );
	
    //cout << "conponents#: " << num << endl;
	
    if( num == n ) { // no any merge
	//	cout << "Info: no component to shrink." << endl;
	return;
    }

    // build a map for component number and vertex
    std::multimap<int, Vertex> comp_map;
	
    graph_traits<Graph>::vertex_iterator vi, vi_end;
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
	comp_map.insert( std::make_pair( component[ g[*vi].id ], *vi ) );
    }
	
    // for each componet with more than one vertices
    std::multimap<int, Vertex>::iterator pos;
	
    int num_comp; // # component
    Vertex new_v; // temp vertex
    Vertex old_v; // old vertex, to remove
	
    pos = comp_map.begin();
    while( pos != comp_map.end() ) {
		
	num_comp = pos->first;
		
	// assertion
	assert( pos == comp_map.lower_bound( num_comp ) );
		
	if( ++comp_map.lower_bound( num_comp ) == comp_map.upper_bound( num_comp ) ) {
	    // only one vertex for this component
	    ++pos;
	    continue;
	}
		
	new_v = add_vertex( g );
		
	// need to shrink
	for( ; pos != comp_map.upper_bound( num_comp ); ++pos ) {
			
	    old_v = pos->second; // get the vertex
			
	    // copy all edges for the new vertex
	    bool hasEdge = false;
	    Vertex src, dst;
	    Edge e;
	    graph_traits<Graph>::in_edge_iterator ei, eiend;
			
	    // connect to all incoming edges
	    for( tie(ei, eiend) = in_edges( old_v, g ); ei != eiend; ++ei ) {
		src = source( *ei, g );
				
		tie( e, hasEdge ) = edge( src, new_v, g );
		if( !hasEdge && (src != new_v) ) {
		    add_edge( src, new_v, g );
		}
	    }
			
	    // connect to all outgoing edges
	    graph_traits<Graph>::out_edge_iterator eo, eoend;
	    for( tie( eo, eoend ) = out_edges( old_v, g ); eo != eoend; ++eo ) {
		dst = target( *eo, g );
				
		tie( e, hasEdge ) = edge( new_v, dst, g );
		if( !hasEdge && (new_v != dst) ) {
		    add_edge( new_v, dst, g );
		}
	    }
			
	    // delete this vertex
	    clear_vertex( old_v, g ); // remove all edges
	    remove_vertex( old_v, g );
	}
    }

    size_t i = 0;
    for (tie(vi, vi_end) = vertices(g) ; vi != vi_end; ++vi ) {
	g[*vi].id = i;
	++i;
    }

}



// find a spanning tree such that it's optimal in terms of minimizing
// the transtive link table
void LabelHelper::findSpanTree( set<Vertex>& roots ) {
    std::set<Vertex>::iterator iter;
    for( iter = roots.begin(); iter != roots.end(); ++iter ) {	
	dfsSpanTree( *iter );
    }		
}

void LabelHelper::dfsSpanTree(Vertex v) {
    if( g[v].x == 1 ) {
	return;
    }
	
    g[v].x = 1; // mark as accessed

    Vertex c;
    graph_traits<Graph>::out_edge_iterator eo, eoend;
    for( tie( eo, eoend ) = out_edges( v, g ); eo != eoend; ++eo ) {
	c = target( *eo, g );
	if( g[c].x == 0 ) { // unaccessed
	    g[*eo].tree = true;
	    dfsSpanTree( c );
	}else{
	    g[*eo].tree = false;
	}
    }	
}

// store all nodes with 0 in-degree into roots
void LabelHelper::getRoots( set<Vertex>& roots ) {

    roots.clear();
    // iterator	
    graph_traits<Graph>::vertex_iterator vi, vi_end;
	
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
	if( in_degree( *vi, g ) == 0 ) {
	    roots.insert( *vi ); // insert all roots of spanning tree
	}
    }
	
}

// assign interval labels as well as non-tree labels
void LabelHelper::assignIntervals( set<Vertex>& roots ) 
{
    count = -1; // initialize the counter
    std::set<Vertex>::iterator iter;
    for( iter = roots.begin(); iter != roots.end(); ++iter ) 
    {	
	// depth-first-search
	dfsInterval( *iter );
    }

    /* DEBUG
    set<Vertex>::iterator rit;
    cout << "roots" << endl;
    for( rit = roots.begin(); rit!= roots.end(); ++rit ) 
    {
	cout << "v[" << g[*rit].id << "]: [" << g[*rit].begin << ", " << g[*rit].end << "]" << endl;
    }
    //show all nodes' interval labeling
    graph_traits<Graph>::vertex_iterator vi, vi_end;    
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) 
    {
	cout << g[*vi].id << ": [" << g[*vi].begin << ", " << g[*vi].end << "]" << endl;
    }
    */
    
}
// depth frist search for assiging interval labels
void LabelHelper::dfsInterval( Vertex v ) 
{
    count++;
    g[v].begin = count; // assign begin value

    int smallest = numeric_limits<int>::max();
    int largest = numeric_limits<int>::min();

    // v has incoming link, push into stack
    if( in_degree(v,g) > 1 ) 
    {
	stack.push_front( count );
    }

    // v has outgoing link
    Vertex c;
    graph_traits<Graph>::out_edge_iterator eo, eoend;
    for( tie( eo, eoend ) = out_edges( v, g ); eo != eoend; ++eo ) 
    {
	// there exists any outgoing link
	if( g[*eo].tree == false ) 
	{ 
	    smallest = count - 1;
	    largest = count;
	    break;
	}		
    }
    // for children
    for( tie( eo, eoend ) = out_edges( v, g ); eo != eoend; ++eo ) 
    {	
	if( g[*eo].tree == false ) { // non-tree edge, ignore
	    continue;
	}		
	// recursively search
	c = target( *eo, g );
	dfsInterval( c );
	//update smallest and largest
	smallest = min( g[c].x, smallest );
	largest = max( g[c].y, largest );		
    }
    // set non-tree labels
    g[v].x = smallest;
    g[v].y = largest;
    if( stack.empty() ) {
	g[v].z = numeric_limits<int>::min();
    }else{
	g[v].z = stack.front();
    }
    // v has incoming link
    if( in_degree( v, g ) > 1 ) {
	stack.pop_front();
    }
    g[v].end = count; // assign end value
}

void LabelHelper::assignNonTree( set<Vertex>& roots ) {
    Edge e;
    Vertex u;
    graph_traits<Graph>::edge_iterator e_it, eend_it;
    for( tie( e_it, eend_it ) = edges( g ); e_it != eend_it; ++e_it ) {
	e = *e_it;
	if( g[e].tree == true ) { // tree edge, do nothing			
	    continue;
	}
	// for each non-tree edge
	u = source( e, g );
	X.insert( g[u].begin );
    }
    X.insert( numeric_limits<int>::max() );
//	cout << "X" << endl;
//	for( Xiter = X.begin(); Xiter != X.end(); ++Xiter ) {
//		cout << *Xiter << endl;
//	}
//	cout << endl << endl;
    Xiter = X.begin();
    idx = 0;
    std::set<Vertex>::iterator iter;
    for( iter = roots.begin(); iter != roots.end(); ++iter ) {	
	// depth-first-search
	dfsNonTree( *iter );
    }

}

void LabelHelper::dfsNonTree( Vertex v ) {
    if( g[v].begin > *Xiter ) {
	++Xiter;
	++idx;
    }
    int nx = idx;
    // v has incoming link, push into stack
    if( in_degree(v,g) > 1 ) {
	stack.push_front( g[v].begin );
    }
    // for children
    Vertex c;
    graph_traits<Graph>::out_edge_iterator eo, eoend;
    for( tie( eo, eoend ) = out_edges( v, g ); eo != eoend; ++eo ) {
	if( g[*eo].tree == false ) { // non-tree edge, ignore
	    continue;
	}		
	// recursively search
	c = target( *eo, g );
	dfsNonTree( c );
    }
    if( (g[v].end+1) > *Xiter ) {
	++Xiter;
	++idx;
    }
	
    // set non-tree labels
    g[v].x = nx;
    g[v].y = idx;
    if( stack.empty() ) {
	g[v].z = numeric_limits<int>::min();
    }else{
	g[v].z = stack.front();
    }
    // v has incoming link
    if( in_degree( v, g ) > 1 ) {
	stack.pop_front();
    }
	
}


// update the map of begin -> end
void LabelHelper::updateIntervalMap( map<int, int>& b2e ) {

    graph_traits<Graph>::vertex_iterator vi, vi_end;	
    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
	b2e.insert( make_pair( g[*vi].begin, g[*vi].end ) );
    }
}	
